Skip to main content

Longest Repeating Character Replacement

Question​

What is the longest substring of a given string that can be formed by replacing at most k characters with any other character?

Example 1
None

Solution​

all//Longest Repeating Character Replacement.py


def longestRepeatingCharacterReplacement(s, k):
    window_start, max_length, max_repeat_letter_count = 0, 0, 0
    frequency_map = {}

    for window_end in range(len(s)):
        right_char = s[window_end]
        frequency_map[right_char] = frequency_map.get(right_char, 0) + 1
        max_repeat_letter_count = max(max_repeat_letter_count, frequency_map[right_char])

        # Current window size is from window_start to window_end,
        # which contains repeating letter characters,
        # thus we can replace a letter in the current window
        # with any other desired letter to get a palindrome
        if window_end - window_start + 1 - max_repeat_letter_count > k:
            left_char = s[window_start]
            frequency_map[left_char] -= 1
            window_start += 1

        max_length = max(max_length, window_end - window_start + 1)
    return max_length


# Test
s = "aabccbb"
k = 2
print(longestRepeatingCharacterReplacement(s, k))
# Output: 5